package com.codejam2013.round1c;

import java.io.File;
import java.io.PrintStream;
import java.util.Arrays;
import java.util.Scanner;


public class A {

	static int nTest;
	static String name;
	static int n, nInt;
	static interval[] its;
	public static void main(String[] args) throws Exception {
		Scanner scanner = new Scanner(new File("A-in.txt"));
		PrintStream ps = new PrintStream(new File("A-out.txt"));
		System.setOut(ps);
		nTest = scanner.nextInt();
		for (int test=1;test<=nTest;++test) {
			name = scanner.next();
			n = scanner.nextInt();
			int L = name.length();
			long val = 0;
			its = new interval[L];
			nInt = 0;
			for (int i=0;i<L;++i) {
				if (isconso(name.charAt(i))) {
					int from = i;
					int to = i;
					while (to < L && isconso(name.charAt(to))) {
						to++;
					}
					i = to;
					to--;
					if (to - from + 1 >= n) {
						interval itv = new interval(from, to);
						its[nInt] = itv;
						nInt++;
					}
				}
			}
			if (nInt > 0) {
				Arrays.sort(its, 0, nInt);
				int last = 0;
				for (int i=0;i<nInt;++i) {
					interval itv = its[i];
					int head = itv.from - last;
					int temp = itv.from + n - 1;
					int tail = L - temp;
					val += (long)head * (long)tail;
					last = itv.to + 1;
					for (int j=itv.from;j<=itv.to;++j) {
						temp = j + n - 1;
						if (temp <= itv.to) {
							tail = L - temp;
							val += tail;
						}
						else {
							int nxt = i + 1;
							if (nxt < nInt) {
								temp = its[nxt].from + n - 1;
								tail = L - temp;
								val += tail;
							}
						}
					}
				}
				
			}
			System.out.println("Case #" + test + ": " + val);
		}

	}
	
	private static boolean isconso(char c) {
		if (c == 'a') return false;
		if (c == 'e') return false;
		if (c == 'i') return false;
		if (c == 'u') return false;
		if (c == 'o') return false;
		return true;
	}

}

class interval implements Comparable<interval> {
	public interval(int from, int to) {
		this.to = to;
		this.from = from;
	}
	int from;
	int to;
	public int compareTo(interval i) {
		return this.from - i.from;
	}
}
